package one.chapter_3;

import com.sun.org.apache.regexp.internal.REDebugCompiler;

public class RedBlackBST<Key extends Comparable<Key>, Value> implements SeqST<Key, Value> {

    private Node root;

    @Override
    public Key min() {
        return null;
    }

    @Override
    public Key max() {
        return null;
    }

    @Override
    public Key floor(Key key) {
        return null;
    }

    @Override
    public Key ceiling(Key key) {
        return null;
    }

    @Override
    public int rank(Key key) {
        return 0;
    }

    @Override
    public Key select(int k) {
        return null;
    }

    @Override
    public void deleteMin() {
        if (!isRed(root.left) && !isRed(root.right)){
            root.color=Node.RED;
        }

        root=deleteMin(root);
        if (!isEmpty()){
            root.color=Node.BLACK;
        }
    }

    private Node deleteMin(Node node) {
        if (node.left==null){
            return null;
        }
        if (!isRed(node.left) && !isRed(node.left.left)){
            node=moveRedLeft(node);
        }
        node.left=deleteMin(node.left);
        return balance(node);
    }

    private Node balance(Node node) {
        return null;
    }

    private Node moveRedLeft(Node node) {

        return null;
    }

    @Override
    public void deleteMax() {

    }

    @Override
    public int size(Key lo, Key hi) {
        return 0;
    }

    @Override
    public Iterable<Key> keys(Key lo, Key hi) {
        return null;
    }

    @Override
    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = Node.BLACK;
    }

    private Node put(Node node, Key key, Value value) {
        if (node == null) {
            return new Node(key, value, 1, Node.RED);
        }
        int cmp = node.key.compareTo(key);
        if (cmp > 0) {
            //放入左子树中
            node.left = put(node.left, key, value);
        } else if (cmp == 0) {
            //已有相应的key，更新value
            node.value = value;
        } else {
            //放入右子树
            node.right = put(node.right, key, value);
        }


        //右孩子为红，左孩子为黑->左旋
        if (isRed(node.right) && !isRed(node.left)) {
            node = rotateLeft(node);
        }

        //左孩子为红，左孩子的左孩子也为红->右旋
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node);
        }

        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node);
        }

        node.N = size(node.left) + size(node.right) + 1;

        return node;
    }

    private void flipColors(Node node) {
        node.color=Node.RED;
        node.left.color=Node.BLACK;
        node.right.color=Node.BLACK;
    }

    private Node rotateRight(Node node) {
        Node x = node.left;
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = Node.RED;
        x.N = node.N;
        node.N = 1 + size(node.left) + size(node.right);
        return x;

    }

    private Node rotateLeft(Node node) {
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = Node.RED;
        x.N = node.N;
        node.N = size(node.left) + size(node.right) + 1;

        return x;
    }

    public boolean isRed(Node node) {
        return node.color == Node.RED;
    }

    @Override
    public Value get(Key key) {
        return null;
    }

    @Override
    public void delete(Key key) {

    }

    @Override
    public Iterable<Key> keys() {
        return null;
    }

    @Override
    public boolean contains(Key key) {
        return false;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return size(root);
    }

    public int size(Node node) {
        return node.N;
    }

    private class Node {
        Key key;
        Value value;
        Node left;
        Node right;
        int N;
        boolean color;
        static final boolean BLACK = false;
        static final boolean RED = true;

        public Node(Key key, Value value, int N, boolean color) {
            this.key = key;
            this.value = value;
            this.N = N;
            this.color = color;
        }

    }


}
